import leetcodeHis.ListNode;
import test0ne.TreeNode;

import java.util.*;
import java.util.concurrent.*;

/**
 * @Author zhang lei
 * @Date 2021-12-22 14:39
 */
public class Test211222 {

    public static void main(String[] args) throws ExecutionException, InterruptedException {
        int[][] array = {{1,   4,  7, 11, 15},
                {2,   5,  8, 12, 19},
                {3,   6,  9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}};

//        System.out.println(minArray(arr));
//        List<List<Integer>> list = permute(new int[]{1,2,3});
//        for (List<Integer> integers : list) {
//            for (Integer integer : integers) {
//                System.out.print(integer+",");
//            }
//            System.out.println();
//        }
        ListNode listNode = new ListNode(-1);
        ListNode cur = listNode;
        int[] arr = new int[]{3,5};
        for (int i : arr) {
            cur.next = new ListNode(i);
            cur = cur.next;
        }

//        System.out.println(reverseBetween(listNode.next,1,2));byte[] bytes = b;
        exist();
    }

    public static boolean exist() {
        BitSet bitSet = new BitSet(100);
        for (int i = 0; i < 100; i++) {
            if (i!=50) {
                bitSet.set(i);
            }
        }
        System.out.println(bitSet.get(50));
        System.out.println(bitSet.get(49));

        return true;
    }

    /**
     * 61旋转链表
     * @param head
     * @param k
     * //输入：head = [1,2,3,4,5], k = 2
     * //输出：[4,5,1,2,3]
     * @return
     */
    public static ListNode rotateRight(ListNode head, int k) {
        //走k+1步骤
        ListNode slow = head;
        ListNode fast = head;

        while (k-- > 0) {
            if(fast.next != null) {
                fast = fast.next;
            }else {
                fast = head;
            }
        }
        while (fast.next!= null) {
            slow = slow.next;
            fast = fast.next;
        }
        ListNode next = slow.next;

        if(next == null) {
            return head;
        }
        slow.next = null;
        fast.next = head;
        return next;
    }

    public static ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode index = dummy;
        while (index.next!= null) {
            ListNode cur = index.next;
            if(cur.val == left) {
                index.next = reverseListNode(cur, right);
                return dummy.next;
            }
            index = index.next;
        }
        return dummy.next;
    }

    private static ListNode reverseListNode(ListNode head, int right) {
        ListNode pre = null, cur = head, next = head;
        while (next != null) {
            next = next.next;

            cur.next = pre;
            pre = cur;
            cur = next;

            if(pre.val == right) {
                head.next = next;
                return pre;
            }
        }
        return null;
    }

    /**
     * 全排列
     * @param nums
     * @return
     */
    public static List<List<Integer>> permute(int[] nums) {
        Set<List<Integer>> result = new HashSet<>();
        List<Integer> cur = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            cur.add(nums[i]);
        }
        result.add(cur);

        for (int i = 0; i < nums.length; i++) {
            List<Integer> cc = new ArrayList<>(cur);
            int temp = cc.get(i);
            cc.set(i, cc.get(0));
            cc.set(0, temp);
            for (int j = 0; j < nums.length; j++) {
                    List<Integer> list = new ArrayList<>(cc);
                    int s = list.get(i);
                    list.set(i, list.get(j));
                    list.set(j, s);
                    result.add(list);
            }
        }
        return new ArrayList<>(result);
    }

    /**
     * 跳台阶
     * @param nums
     * @return
     */
    public static int jump(int[] nums) {
        int[] dp = new int[nums.length];

        dp[0] = 0;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if(nums[j] >= (i-j)) {
                    dp[i] = Math.min(dp[i], dp[j]+1);
                }
            }
        }
        return dp[nums.length-1];
    }


    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        Arrays.sort(candidates);
        findResult(candidates, target, result, cur, 0);
        return result;
    }

    private static void findResult(int[] candidates, int target, List<List<Integer>> result, List<Integer> cur, int index) {
        if(index == candidates.length) {
            return;
        }

        if(target == 0) {
            result.add(new ArrayList<>(cur));
            return;
        }

        findResult(candidates, target, result, cur, index+1);

        if(target >= candidates[index]) {
            if(cur.size() == 0 && index>0 && candidates[index] == candidates[index-1]) {
                findResult(candidates, target, result, cur, index+1);
            }else {
                cur.add(candidates[index]);
                findResult(candidates, target - candidates[index], result, cur, index+1);
                cur.remove(cur.size() - 1);
            }
        }
    }

    /**
     * 在排序数组中查找元素的第一个和最后一个位置
     * @param nums
     * @param target
     * @return
     */
    public static int[] searchRange(int[] nums, int target) {
        int l = 0, r = nums.length-1;
        int[] result = new int[]{-1,-1};
        //先找左边的
        while (l<=r) {
            int mid = l + (r-l)/2;
            if(nums[mid] == target) {
                if(mid == 0 || nums[mid-1] != target) {
                    result[0] = mid;
                    break;
                }else if(nums[mid-1] == target) {
                    r = mid - 1;
                }
            }else if(nums[mid] > target) {
                r = mid-1;
            }else {
                l = mid +1;
            }
        }

        r = nums.length-1;
        while (l<=r) {
            int mid = l + (r-l)/2;
            if(nums[mid] == target) {
                if(mid == nums.length-1 || nums[mid+1] != target) {
                    result[1] = mid;
                    break;
                }else if(nums[mid+1] == target) {
                    l = mid + 1;
                }
            }else if(nums[mid] > target) {
                r = mid-1;
            }else {
                l = mid +1;
            }
        }
        return result;
    }

    /**
     * 旋转数组的查找
     * @param nums
     * @param target
     * @return
     */
    public static int search(int[] nums, int target) {
        int l = 0, r = nums.length-1;

        while (l<=r) {
            int mid = l + (r-l)/2;

            if(nums[mid]>=nums[r] && nums[mid]>=nums[l]) {
                //第一个上升通道
                if(target>=nums[l] && target<=nums[mid]) {
                    if(target == nums[l]) {return l;}
                    if(target == nums[mid]) {return mid;}
                    r = mid-1;
                }else {
                    l = mid+1;
                }
            }else {
                if(target>=nums[mid] && target<=nums[r]) {
                    if(target == nums[mid]) {return mid;}
                    l = mid+1;
                }else {
                    r = mid-1;
                }
            }

        }
        return -1;
    }

    public static Boolean find(TreeNode a, TreeNode b) {
        if(a==null || b==null) {
            return false;
        }
        return doesHas(a, b)|| find(a.left, b) || find(a.right, b);
    }

    private static Boolean doesHas(TreeNode a, TreeNode b) {
        if(b == null) {
            return true;
        }
        if(a == null) {
            return false;
        }
        if(a.val.equals(b.val)) {
            return doesHas(a.left, b.left) && doesHas(a.right, b.right);
        }
        return false;
    }


    /**
     * 替换空格
     * @param s
     * @return
     */
    public static String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.toCharArray().length; i++) {
            if(s.charAt(i) == ' ') {
                sb.append("%20");
            }else {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }

    /**
     * 【重要】旋转数组的最小值
     * @param numbers
     * @return
     */
    public static int minArray(int[] numbers) {
        int l = 1;
        int r = numbers.length-1;
        while (l<=r) {
            int mid = l+(r-l)/2;

            if(mid == 0 || numbers[mid]<numbers[mid-1]) {
                return numbers[mid];
            } else if(numbers[mid] > numbers[r]) {
                l=mid+1;
            }else if(numbers[mid] <numbers[r]) {
                r = mid-1;
            }else {
                r -= 1;
            }
        }
        return numbers[0];
    }


    /**
     * 给定在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个
     * 整数，判断数组中是否含有该整数
     * @param matrix
     * @param target
     * @return
     */
    Map<String, Boolean> map = new HashMap<>();

    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int row = matrix.length;
        int col = matrix[0].length;

        return findNumberIn2DArray2(matrix, target, row-1, col-1);
    }

    private boolean findNumberIn2DArray2(int[][] matrix, int target, int i, int j) {
        if(i<0 || j<0) {
            return false;
        }
        boolean result = false;
        String key = i+","+j;
        if(map.get(key) != null) {
            result = map.get(key);
        }else {
            int cur = matrix[i][j];
            if (cur == target) {
                result = true;
            } else if (cur > target) {
                result = findNumberIn2DArray2(matrix, target, i - 1, j) || findNumberIn2DArray2(matrix, target, i, j - 1);
            }
            map.put(key, result);
        }

        return result;
    }

}
